package com.czm.test;


import java.util.*;

/**
 * @author CZM
 * @date 2022 06 18 12:06
 */
public class Day02 {
    public static void main(String[] args) {
        // test011();
        // test012();
        // test013();
        // test();
        test014();
        Set<String> set = new HashSet<>();
        set.add("aa");
        set.add("bb");
        set.add("vv");
        set.add("dd");
        for (String s : set) {
            if (s.equals("bb")) {
                set.remove(s);
            }
        }
        for (String s : set) {
            System.out.println(s);
        }
    }

    /**
     * 题目描述：
     * 二叉树也可以用数组来存储，
     * 给定一个数组，树的根节点的值储存在下标1，
     * 对于储存在下标n的节点，他的左子节点和右子节点分别储存在下标2*n和2*n+1，
     * 并且我们用-1代表一个节点为空，
     * 给定一个数组存储的二叉树，
     * 试求从根节点到最小的叶子节点的路径，
     * 路径由节点的值组成。
     * <p>
     * 输入描述
     * 输入一行为数组的内容，
     * 数组的每个元素都是正整数，元素间用空格分割，
     * 注意第一个元素即为根节点的值，
     * 即数组的第n元素对应下标n，
     * 下标0在树的表示中没有使用，所以我们省略了，
     * 输入的树最多为7层。
     * <p>
     * 输出描述
     * 输出从根节点到最小叶子节点的路径上各个节点的值，
     * 由空格分割，
     * 用例保证最小叶子节点只有一个。
     * <p>
     * 示例一
     * 输入
     * 3 5 7 -1 -1 2 4
     * 输出
     * 3 7 2
     * 示例二
     * 输入
     * 5 9 8 -1 -1 7 -1 -1 -1 -1 -1 6
     * 输出
     * 5 8 7 6
     */
    // 解题思路：找出除了根节点的最小节点，除以2得到的整数就是它的父节点，依次除下去，直至根节点
    // 树根节点到最小的叶子节点的路径
    public static void test011() {
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        String[] s = line.split(" ");
        // 只输入一个根元素，直接返回
        if (s.length <= 1) {
            System.out.println(s[0]);
            return;
        }
        List<Integer> list = new ArrayList<>();
        // 集合第一个元素是无关元素，存个最大的整型数
        list.add(Integer.MAX_VALUE);
        for (int i = 0; i < s.length; i++) {
            list.add(Integer.parseInt(s[i]));
        }
        // 找出最小的数，-1表示该节点为空，不参与查找
        int res = Integer.MAX_VALUE;
        for (int i = 2; i < list.size(); i++) {
            if (list.get(i) != -1) {
                res = Math.min(res, list.get(i));
            }
        }
        // 找不到最小的数，说明树除了根元素，其他都是-1
        if (res == Integer.MAX_VALUE) {
            System.out.println(s[0]);
            return;
        }
        // 找出最小的数所在位置
        int resKey = 0;
        for (int i = 2; i < list.size(); i++) {
            if (list.get(i) == res) {
                resKey = i;
            }
        }
        // 用于储存结果
        List<Integer> resList = new ArrayList<>();
        while (resKey != 1) {
            resList.add(resKey);
            resKey = resKey / 2;
        }
        // 添加根元素
        resList.add(1);
        for (int i = resList.size() - 1; i >= 0; i--) {
            System.out.print(list.get(resList.get(i)) + " ");
        }
    }

    /**
     * 题目描述：
     * 一辆运送快递的货车，
     * 运送的快递放在大小不等的长方体快递盒中，
     * 为了能够装载更多的快递同时不能让货车超载，
     * 需要计算最多能装多少个快递。
     * 注：快递的体积不受限制。
     * 快递数最多1000个，货车载重最大50000。
     * <p>
     * 输入描述
     * 第一行输入每个快递的重量
     * 用英文逗号隔开
     * 如 5,10,2,11
     * 第二行输入货车的载重量
     * 如 20
     * <p>
     * 输出描述
     * 输出最多能装多少个快递
     * 如 3
     * <p>
     * 示例一
     * 输入
     * 5,10,2,11
     * 20
     * 输出
     * 3
     */
    // 货车最大载货量
    public static void test012() {
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        int capacity = sc.nextInt();
        String[] split = line.split(",");
        // 将字符串数组转为Integer型集合
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < split.length; i++) {
            list.add(Integer.parseInt(split[i]));
        }
        // 对集合进行排序
        Collections.sort(list);
        int sum = 0;
        for (int i = 0; i < list.size(); i++) {
            if (sum + list.get(i) < capacity) {
                sum = sum + list.get(i);
            } else {
                System.out.println(i);
                return;
            }
        }
    }

    /**
     * 题目描述：
     * 给航天器一侧加装长方形和正方形的太阳能板(图中的斜线区域);
     * 需要先安装两个支柱(图中的黑色竖条);
     * 再在支柱的中间部分固定太阳能板;
     * 但航天器不同位置的支柱长度不同;
     * 太阳能板的安装面积受限于最短一侧的那支支柱的长度;
     * <p>
     * 现提供一组整型数组的支柱高度数据;
     * 假设每个支柱间的距离相等为一个单位长度;
     * 计算如何选择两根支柱可以使太阳能板的面积最大;
     * <p>
     * 输入描述
     * 10,9,8,7,6,5,4,3,2,1
     * 注释，支柱至少有两根，最多10000根，能支持的高度范围1~10^9的整数
     * <p>
     * 柱子的高度是无序的
     * 例子中的递减是巧合
     * <p>
     * 输出描述
     * 可以支持的最大太阳板面积:(10m高支柱和5m高支柱之间)
     * 25
     * <p>
     * 示例一
     * 输入
     * 10,9,8,7,6,5,4,3,2,1
     * 输出
     * 25
     * 备注
     * 10米高支柱和5米高支柱之间宽度为5，高度取小的支柱高度也是5，面积为25
     * 任取其他两根支柱所能获得的面积都小于25 所以最大面积为25
     */
    // 没图 题目大概的意思就是：数组两个元素的间距 乘以 两个元素中的最小值，取最大的，就是太阳能板的最大面积了
    // 太阳能板最大面积
    public static void test013() {
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        String[] split = line.split(",");
        int len = split.length;
        // 结果
        int res = 0;
        for (int i = 0; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++) {
                int eare = Math.min(Integer.parseInt(split[i]), Integer.parseInt(split[j])) * (j - i);
                res = Math.max(res, eare);
            }
        }
        System.out.println(res);
    }

    /**
     * 题目描述：
     * 单词接龙的规则是:
     * 可用于接龙的单词,首字母必须要与前一个单词的尾字母相同；
     * 当存在多个首字母相同的单词时，取长度最长的单词；
     * 如果长度也相等，则取字典序最小的单词；
     * 已经参与接龙的单词不能重复使用；
     * 现给定一组全部由小写字母组成的单词数组，
     * 并指定其中一个单词为起始单词，进行单词接龙，
     * 请输出最长的单词串。
     * 单词串是单词拼接而成的，中间没有空格。
     * <p>
     * 单词个数 1 < N < 20
     * 单个单词的长度 1 ~ 30
     * <p>
     * 输入描述
     * 输入第一行为一个非负整数
     * 表示起始单词在数组中的索引k
     * 0 <= k < N
     * 输入的第二行为非负整数N
     * 接下来的N行分别表示单词数组中的单词
     * <p>
     * 输出描述
     * 输出一个字符串表示最终拼接的单词串
     * <p>
     * 示例一
     * 输入
     * 0
     * 6
     * word
     * dd
     * da
     * dc
     * dword
     * d
     * 输出
     * worddwordda
     * 示例二
     * 输入
     * 4
     * 6
     * word
     * dd
     * da
     * dc
     * dword
     * d
     * 输出
     * dwordda
     */
    // PS：如果给出的单词中同样的单词出现两次，能用两次还是用一次？我这里是用了两次，如果只能用一次的话，可以用一个list来存储用过的单词，如果在里面，就不用
    // 单词接龙
    public static void test014() {
        Scanner sc = new Scanner(System.in);
        int start = Integer.parseInt(sc.nextLine());
        int len = Integer.parseInt(sc.nextLine());
        List<String> list = new ArrayList<>();
        Set<String> set = new HashSet<>();
        for (int i = 0; i < len; i++) {
            list.add(sc.nextLine());
        }
        String startWord = list.get(start);
        // 移除起始元素
        list.remove(startWord);
        list.sort((s1, s2) -> {
            int length1 = s1.length();
            int length2 = s2.length();
            if (length1 != length2) {
                return length2 - length1;
            }
            char[] chars1 = s1.toCharArray();
            char[] chars2 = s2.toCharArray();
            int sum1 = 0;
            int sum2 = 0;
            for (int i = 0; i < chars1.length; i++) {
                sum1 = sum1 + chars1[i];
                sum2 = sum2 + chars2[i];
            }
            return sum1 - sum2;
        });
        String result = startWord;
        for (int i = 0; i < list.size(); i++) {
            String value = list.get(i);
            if (getStartOrEnd(startWord, 100).equals(getStartOrEnd(value, 1))) {
                result = result + value;
                // 找到的单词作为起始单词
                startWord = value;
                // 移除用过的单词
                list.remove(value);
                // 找到了归零，下一个从头开始找
                i = 0;
            }
        }
        System.out.println(result);
    }

    private static String getStartOrEnd(String key, int num) {
        // 求字符串首字母
        if (num == 1) {
            return key.substring(0, 1);
        } else { // 求字符串尾字幕
            return key.substring(key.length() - 1, key.length());
        }
    }

    public static void test014_2() {
        Scanner in = new Scanner(System.in);

        int k = Integer.parseInt(in.nextLine());
        int N = Integer.parseInt(in.nextLine());
        ArrayList<String> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            list.add(in.nextLine());
        }

        StringBuilder builder = new StringBuilder();
        String head = list.get(k);
        builder.append(head);
        list.remove(k);

        String tail = head.substring(head.length() - 1);

        while (true) {
            TreeSet<String> set = new TreeSet<>();

            for (int i = 0; i < list.size(); i++) {
                String word = list.get(i);
                if (word.startsWith(tail)) {
                    set.add(word);
                }
            }
            if (set.size() == 0) break;
            String first = set.pollFirst();
            int len = first.length();
            String aim = "";
            for (String s : set) {
                if (s.length() > len) {
                    len = s.length();
                    aim = s;
                }
            }
            String into = len != first.length() ? aim : first;
            tail = into.substring(into.length() - 1);
            builder.append(into);
            list.remove(into);
        }
        System.out.println(builder.toString());

        in.close();
    }


    /**
     *给定一个字符串
     只包含大写字母
     求在包含同一字母的子串中
     长度第K长的子串
     相同字母只取最长的子串

     输入
     第一行 一个子串 1<len<=100
     只包含大写字母
     第二行为k的值

     输出
     输出连续出现次数第k多的字母的次数

     例子：
     输入
     AABAAA
     2
     输出
     1
     同一字母连续出现最多的A 3次
     第二多2次  但A出现连续3次

     输入
     AAAAHHHBBCDHHHH
     3
     输出
     2
     //如果子串中只包含同一字母的子串数小于k
     则输出-1
     */
    public static void test017() {
    }

    /**
     *
     */
    public static void test018() {
    }

    /**
     *
     */
    public static void test019() {
    }
}
